package hard;

import java.util.*;

public class ladderLength {
    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 第 1 步：先将 wordList 放到哈希表里，便于判断某个单词是否在 wordList 里
        Set<String> wordSet = new HashSet<>(wordList);
        if (wordSet.size() == 0 || !wordSet.contains(endWord)) {
            return 0;
        }
        wordSet.remove(beginWord);
        Queue<String> queue=new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited=new HashSet<>();
        visited.add(beginWord);
        int step=1;
        while (!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;++i){
                String currentWord = queue.poll();
                if(changeWordEveryOneLetter(currentWord,endWord,
                        queue,visited,wordSet)){
                    return step+1;
                }
            }
        }
        return step;

    }

    private static boolean changeWordEveryOneLetter(String word, String endWord,
                                             Queue<String> queue,
                                             Set<String> visited,
                                             Set<String> wordSet) {
        char[] charArray = word.toCharArray();
        for (int i = 0; i < word.length(); i++) {
            char originChar = charArray[i];
//            对word进行转换
            for (char c = 'a'; c <= 'z'; c++) {
                if (originChar == c) {
                    continue;
                }
                charArray[i] = c;
                String nextWord = String.valueOf(charArray);
                if (wordSet.contains(nextWord)) {
                    if (nextWord.equals(endWord)) {
                        return true;
                    }
                    if (!visited.contains(nextWord)) {
                        queue.add(nextWord);
                        visited.add(nextWord);
                    }
                }
            }
            // 恢复，下次再用
            charArray[i] = originChar;
        }
        return false;
    }

    public static void main(String[] args) {
        String[] wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
        System.out.println(ladderLength("hit",
                "cog",
                Arrays.asList(wordList)));

    }

}
